package leetcode.stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author way
 * @create 2025-03-04 21:10
 * 从左往右写，栈中元素还没有找到下一个更大的数，，一旦发现一个比栈顶大的数，就立刻更新栈顶的答案，同时栈顶元素出栈。
 * 及时去掉无用数据，保证栈中数据有序。
 */
public class _739_dailyTemperatures {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] ans = new int[temperatures.length];
        Deque<Integer> stack = new LinkedList<>();

        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int j = stack.pop();
                ans[j] = i - j;
            }
            stack.push(i);
        }
        return ans;
    }
}
